/**
 * 这是 LeetCode 第 88 题 "合并两个有序数组" 的解决方案
 * 这段代码实现了将两个有序数组 nums1 和 nums2 合并为一个有序数组的功能。具体步骤如下：
 * 初始化指针：定义三个指针 p1、p2 和 p，分别指向 nums1 的最后一个有效元素、nums2 的最后一个元素和合并后数组的最后一个位置。
 * 从后向前比较并填充较大值：使用 while 循环从后向前遍历 nums2，每次比较 nums1[p1] 和 nums2[p2]，将较大的值填入 nums1[p]，并移动相应指针。
 * 处理特殊情况：如果 nums1 的有效元素已经用完，则直接将 nums2 的剩余元素填入 nums1
 * 时间复杂度 O(m+n)
 * 空间复杂度 O(1)
 */
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 初始化三个指针
        // p1 指向 nums1 的最后一个有效元素
        // p2 指向 nums2 的最后一个元素
        // p 指向要填入的位置
        int p1 = m - 1;
        int p2 = n - 1;
        int p = m + n - 1;
        
        // 从后向前比较并填充较大的数
        while (p2 >= 0) {
            // 如果 p1 < 0，说明 nums1 的有效元素已经用完
            // 或者 nums2 当前元素大于 nums1 当前元素
            if (p1 < 0 || nums2[p2] >= nums1[p1]) {
                nums1[p] = nums2[p2];
                p2--;
            } else {
                nums1[p] = nums1[p1];
                p1--;
            }
            p--;
        }
    }

    // 用于打印数组的辅助方法
    private static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // 测试用例 1: 常规情况
        System.out.println("测试用例 1:");
        int[] nums1_1 = new int[]{1,2,3,0,0,0};
        int[] nums2_1 = new int[]{2,5,6};
        System.out.println("合并前:");
        System.out.println("nums1 = ");
        printArray(nums1_1);
        System.out.println("nums2 = ");
        printArray(nums2_1);
        solution.merge(nums1_1, 3, nums2_1, 3);
        System.out.println("合并后:");
        printArray(nums1_1);
        System.out.println();

        // 测试用例 2: nums1 为空
        System.out.println("测试用例 2:");
        int[] nums1_2 = new int[]{0};
        int[] nums2_2 = new int[]{1};
        System.out.println("合并前:");
        System.out.println("nums1 = ");
        printArray(nums1_2);
        System.out.println("nums2 = ");
        printArray(nums2_2);
        solution.merge(nums1_2, 0, nums2_2, 1);
        System.out.println("合并后:");
        printArray(nums1_2);
        System.out.println();

        // 测试用例 3: nums2 为空
        System.out.println("测试用例 3:");
        int[] nums1_3 = new int[]{1};
        int[] nums2_3 = new int[]{};
        System.out.println("合并前:");
        System.out.println("nums1 = ");
        printArray(nums1_3);
        System.out.println("nums2 = ");
        printArray(nums2_3);
        solution.merge(nums1_3, 1, nums2_3, 0);
        System.out.println("合并后:");
        printArray(nums1_3);
        System.out.println();

        // 测试用例 4: 有重复元素
        System.out.println("测试用例 4:");
        int[] nums1_4 = new int[]{1,2,2,0,0,0};
        int[] nums2_4 = new int[]{1,2,3};
        System.out.println("合并前:");
        System.out.println("nums1 = ");
        printArray(nums1_4);
        System.out.println("nums2 = ");
        printArray(nums2_4);
        solution.merge(nums1_4, 3, nums2_4, 3);
        System.out.println("合并后:");
        printArray(nums1_4);
    }
}